package hyy_2022;

/**
 * 统计一个数字在排序数组中出现的次数
 * 可转化为: 使用二分法分别找到左边界left和右边界right, 易得数字target的数量为 right - left - 1
 *
 * 1 2 3 3 3 5  =>  right=5,left=1, 出现的次数= right-left-1 = 3
 */
public class _0815_Offer53_BinarySearch {

    /**
     * 排序数组中的搜索问题,首先想到用二分法解决
     * @param nums
     * @param target
     * @return int
     */
    public int search(int[] nums, int target) {
        //搜索右边界right
        int i = 0;
        int j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        int right = i;
        //若数组中无target,则提前返回
        if(j > 0 && nums[j] != target) {
            return 0;
        }


        //搜索左边界left
        i = 0;
        j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        int left = j;
        return right - left - 1;
    }

}
